// 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

// 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

// 示例 1:
// s = "abc", t = "ahbgdc"

// 返回 true.

// 示例 2:
// s = "axc", t = "ahbgdc"

// 返回 false.

// 后续挑战 :

// 如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::string;
using std::unordered_map;
using std::upper_bound;

// O(n)
class Solution1 {
public:
    bool isSubsequence(string s, string t) {
        if (s.empty()) return true;
        int n = t.size();
        int m = s.size();
        for (int i{0}, j{0}; i < n; ++i) {
            if (t[i] == s[j]) ++j;
            if (j == m) return true;
        }
        return false;
    }
};

/* 双指针
时间复杂度：O(m+n)
空间复杂度：O(1)
*/
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        if (m == 0) return true;
        if (n == 0) return false;
        int i{0};
        int j{0};
        while (i < m && j < n) {
            if (s[i] == t[j]) {
                ++i;
                ++j;
            } else {
                ++j;
            }
        }
        return i == m;
    }
};


/* 动态规划，哈希表
记录对于t的每一个位置，从该位置开始往后每一个字符第一次出现的位置
dp[i][j]表示字符串t从位置i开始往后字符j第一次出现的位置
如果t[i]就是j，那么dp[i][j] = i，否则j出现在位置i+1开始往后，dp[i][j] = dp[i+1][j]
从后往前遍历
时间复杂度：O(m+n)
空间复杂度：O(1)
*/
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();
        vector<vector<int>> dp(m + 1, vector<int>(26, 0));
        for (int i{0}; i < 26; ++i) {
            dp[m][i] = m;
        }
        for (int i{m - 1}; i >= 0; --i) {
            for (int j{0}; j < 26; ++j) {
                if (t[i] == j + 'a') {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int add{0};
        for (int i{0}; i < n; ++i) {
            if (dp[add][s[i] - 'a'] == m) {  // =m就表示找不到
                return false;
            }
            add = dp[add][s[i] - 'a'] + 1;
        }
        return true;
    }
};